In variable length coding, source symbols of a fixed length are encoded with codes of a variable length. Variable length coding is a widely used technique for lossless data compression. VLC has become part of some international standards for various applications, for example, still image coding, video image coding, facsimile coding, and so on.
The variable length coding technique encodes the frequently occurring fixed length source symbols with shorter codes and the infrequently occurring fixed length source symbols with longer codes. Thus, the VLC takes the advantage of a non-uniform distribution in the occurrence of the fixed length source symbols. In general, the length of the code for a fixed length source symbol is designed to be inversely proportional to the probability of the occurrence of the symbol. The most well-known example of a variable length code is the Huffman code.
As the codes are of non-equal length, the encoder should concatenate those codes to form a bit stream without gaps. This may be accomplished using a serial encoder or a parallel encoder. A serial encoder outputs one bit at a time. A parallel encoder outputs a group of bits (e.g., eight) at a time, in parallel. A parallel encoder generally contains circuitry for rearranging the variable length code words into groups of, e.g., eight bits. Conventional VLC techniques are disclosed in M. Stroppiana, L. Ronchetti, Device for reducing the redundancy in blocks of digital video data in DCT encoding U.S. Pat. No. 5006930, 1991.4.9., F. Azadegan, E. Fisch, Method and apparatus for digitally processing a high definition television augmentation signal U.S. Pat. No. 5128758, 1992.7.7., S. M. Lei, M. T. Sun, An Entropy Coding System for Digital HDTV Application, IEEE Trans. on Circuit and system for Video tech., vol. CASV-1, no. 1, pp. 147-155, Feb. 1991, F. Azadegan, Method and apparatus for digitally processing a high definition television augmentation signal, U.S. Pat. No. 5,179,442, 1993.1.12., G. J. Kustka, Variable length decoder, U.S. Pat. No. 5226082, 1993.7.6., K. C. Chu, etc., Variable length decoding using lookup tables, U.S. Pat. No. 5,253,053, 1993.10.12., H. Brusewitz, Method and means for variable length coding, U.S. Pat. No. 492,2510, 1990.5.1., F. Mikami, Variable-length coding/decoding device, U.S. Pat. No. 4,985,700, 1991.1,15., N. Shirota Coding and decoding apparatus of variable length data U.S. Pat. No. 5162795, 1992.11.10., which are incorporated herein by reference.
In most variable length coding systems, the variable length codes are represented by two-field codes. One field stores the code word and the other field records the corresponding code-length. FIG. 1 provides a variable length code for the transform coefficients in CCITT recommendation H.261. There are 127 fixed length source symbols. Each source symbol has two fields designated run and level. The level may be a positive or a negative value. A variable length code is associated with each source symbol. The "s" is "zero" or "one" depending on whether the level is a positive or negative quantity.
FIG. 2 is a table which shows a two-field code associated with each of the fixed length source symbols. One field is the code word length and the other field is the variable length code word itself.
FIG. 3 is a conventional variable length parallel encoder for implementing a codebook using a two-field representation such as shown in FIG. 1 and FIG. 2. The encoder 10 of FIG. 3 comprises two basic sections. The section 12 is a memory or other translation device which receives fixed length source codewords of n bits and outputs the variable length codes in a two field representation. The section 22 concatenates the variable length code words and arranges the variable length code words in groups of, e.g., eight bits for transmission.
In the illustrative encoder 10 of FIG. 3, the translation device 12 is a PLA. The PLA 12 comprises an AND plane 14 which receives the source symbols at the input 15. There are two OR-planes 16 and 18 in the PLA 12. The OR-plane 16 is for outputting the code word and the OR-plane 18 is for outputting the code length. The code word generated by the OR-plane 16 is latched in the register W.sub.o. The code length generated by the OR-plane 18 is latched by the register L.sub.o.
The output of the encoder is obtained from the register W.sub.2 at the output 20. It should be noted that the variable length code words are chosen so that no shorter code comprises a subset of the bits in a longer code. For this reason, a decoder cannot "mistakenly" recognize and decode a shorter code when it is supposed to receive a longer code. Thus, it is not necessary to explicitly transmit the code length information with each variable length code word. Rather, the code length information is used by the circuitry 22 in the encoder 10 to concatenate the variable length code words in groups of bits which are stored in parallel in the register W.sub.2.
The circuitry 22 comprises the barrel shifter BS.sub.1, the barrel shifter BS.sub.2, the code length accumulation circuit 19, and the registers W.sub.1 and W.sub.2. The code length accumulation circuit accumulates the code lengths latched in the register L.sub.0 in each cycle. The barrel shifters BS.sub.1 and BS.sub.2 operate as follows. In each cycle, the contents of W.sub.1 and W.sub.0 are concatenated and left shifted in the combined W.sub.1 W.sub.0 window by BS.sub.1 by a number of spaces determined by L.sub.0. The left most eight bits in the W.sub.1 W.sub.0 window are then written into W.sub.1. The code length accumulation circuit cumulates the contents of L.sub.0 over successive cycles by performing a sum of all code lengths stored in L.sub.0 (.SIGMA.L.sub.0) modulo W where W is the maximum length of the variable length code word (e.g. eight). The value .SIGMA. L.sub.0 mod W on a cycle i is the occupancy of the register W.sub.1 on cycle c+1. In determining .SIGMA. L.sub.0 mod W, the accumulation circuit periodically counts through overflow, i.e., W.
The accumulation circuit 19 outputs an appropriate shift count for the barrel shifter BS.sub.2. In the event the accumulation circuit 19 has not counted through overflow, BS.sub.2 is not enabled. Instead, the entire new variable length code will be shifted into, and concatenated with, the contents of W.sub.1. In the event the accumulation circuit has counted through overflow on a cycle i+1, BS.sub.2 is enabled and provided with the shift count 8 minus the value .SIGMA. L.sub.0 modulus 8 determined for the cycle i. As a result, BS.sub.2 outputs the W=8 left most bits of the shifted window W.sub.1 W.sub.0 for storage in the register W.sub.2, The outputted W=8 bits includes the contents of the register W.sub.1 on the cycle i followed by at least one bit of the new variable length code in W.sub.0 concatenated thereto.
In each cycle where the accumulator circuit cycles through zero, it outputs a control signal to BS.sub.2 to control the shift from window W.sub.1 W.sub.0 to W.sub.2. Thus, this shift will only take place if the window W.sub.1 W.sub.0 contains at least W=8 bits.
FIG. 4 is a table which shows the values of W.sub.0, W.sub.1, W.sub.2, L.sub.0, and .SIGMA. L.sub.0 mod W in an example where W=8 for each of five cycles.
The example encoder shown in FIG. 3 is a conventional parallel encoder. The encoder complexity will depend on the code book. Let the code book length be N and the longest code-length be W. The bit number to represent the code-length will be .left brkt-top.l=log.sub.2 W.right brkt-top. where .left brkt-top.x.right brkt-top. ceiling or least integer less than or equal to x. Let the fixed length source symbol input to the PLA 12 be n bits. We can estimate the gate count required by the components in the encoder of FIG. 3 roughly as follows.
PLA: (n+W+l) N.times.1 gates
registers: (3W+l).times.8 gates
barrel shifters: {2[W+2W]W/2+2Wl}.times.1 gates
accumulator: l.times.8+l.times.9 gates
Totally, the number of gates required by this conventional encoder (which uses a two-field representation for each variable length codeword) is approximately EQU T.sub.0 =(n+W+l)N+25l+24W+3W.sup.2 +2lW.
Therefore, the system complexity (or cost) is approximately proportional to the square of W. As the longest code length increases, the complexity of the encoder will increase. Consider the case where W=14, N=127, n=9, and l=4. In this case T.sub.0 =4565.
In view of the foregoing, it is an object of the invention to provide a VLC encoding technique which utilizes an encoder of reduced complexity.
It is also an object of the invention to provide a VLC encoding technique which reduces the storage requirements of a VLC code book.